#include <bits/stdc++.h>
using namespace std;

/*
2081. k 镜像数字的和
已解答
困难
相关标签
premium lock icon
相关企业
提示
一个 k 镜像数字 指的是一个在十进制和 k 进制下从前往后读和从后往前读都一样的 没有前导 0 的 正 整数。

比方说，9 是一个 2 镜像数字。9 在十进制下为 9 ，二进制下为 1001 ，两者从前往后读和从后往前读都一样。
相反地，4 不是一个 2 镜像数字。4 在二进制下为 100 ，从前往后和从后往前读不相同。
给你进制 k 和一个数字 n ，请你返回 k 镜像数字中 最小 的 n 个数 之和 。

 

示例 1：

输入：k = 2, n = 5
输出：25
解释：
最小的 5 个 2 镜像数字和它们的二进制表示如下：
  十进制       二进制
    1          1
    3          11
    5          101
    7          111
    9          1001
它们的和为 1 + 3 + 5 + 7 + 9 = 25 。
示例 2：

输入：k = 3, n = 7
输出：499
解释：
7 个最小的 3 镜像数字和它们的三进制表示如下：
  十进制       三进制
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
它们的和为 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499 。
示例 3：

输入：k = 7, n = 17
输出：20379000
解释：17 个最小的 7 镜像数字分别为：
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596
 

提示：

2 <= k <= 9
1 <= n <= 30
*/

// 法一
class Solution {
public:
    using ll = long long;
    // 检查数字x在k进制下是否为回文数
    bool isKPalindrome(ll x, int k) {
        ll rev = 0;      // 存储反转后的数字
        ll orig = x;     // 保存原始数字用于比较
        while (x > 0) {
            // 反转数字：每次将x的最后一位添加到rev的末尾
            rev = rev * k + (x % k);
            x /= k;      // 移除x的最后一位
        }
        // 比较反转后的数字和原始数字
        return rev == orig;
    }

    // 寻找前n个k镜像数字的和
    long long kMirror(int k, int n) {
        ll sum = 0;      // 存储符合条件的数字之和
        // 从长度为1的数字开始枚举（1位数、2位数...）
        for (int len = 1; ; len++) {
            // 计算当前长度回文数的前半部分范围
            ll start = pow(10, (len - 1) / 2);
            ll end = pow(10, (len + 1) / 2); // 结束范围（不包含）
            // 生成所有可能的回文数前半部分
            for (ll i = start; i < end; i++) {
                ll palin = i;    // 回文数的前半部分
                ll tmp = len % 2 == 0 ? i : i / 10; // 处理奇数/偶数长度
                // 构造完整的回文数
                while (tmp > 0) {
                    palin = palin * 10 + (tmp % 10); // 添加后半部分
                    tmp /= 10;
                }
                // 检查该回文数在k进制下是否也是回文
                if (isKPalindrome(palin, k)) {
                    sum += palin;  // 累加到总和
                    if (--n == 0)  // 找到n个数字后返回结果
                        return sum;
                }
            }
        }
    }
};


/**
 * 我们可以预处理出 k=2,3,⋯,9 的前 30 个 k 镜像数字，并直接累加返回答案。
 */
// 法二
class Solution {
private:
    static constexpr long long ans[][30] = {
        {1, 3, 5, 7, 9, 33, 99, 313, 585, 717, 7447, 9009, 15351, 32223, 39993, 53235, 53835, 73737, 585585, 1758571, 1934391, 1979791, 3129213, 5071705, 5259525, 5841485, 13500531, 719848917, 910373019, 939474939},
        {1, 2, 4, 8, 121, 151, 212, 242, 484, 656, 757, 29092, 48884, 74647, 75457, 76267, 92929, 93739, 848848, 1521251, 2985892, 4022204, 4219124, 4251524, 4287824, 5737375, 7875787, 7949497, 27711772, 83155138},
        {1, 2, 3, 5, 55, 373, 393, 666, 787, 939, 7997, 53235, 55255, 55655, 57675, 506605, 1801081, 2215122, 3826283, 3866683, 5051505, 5226225, 5259525, 5297925, 5614165, 5679765, 53822835, 623010326, 954656459, 51717171715},
        {1, 2, 3, 4, 6, 88, 252, 282, 626, 676, 1221, 15751, 18881, 10088001, 10400401, 27711772, 30322303, 47633674, 65977956, 808656808, 831333138, 831868138, 836131638, 836181638, 2512882152, 2596886952, 2893553982, 6761551676, 12114741121, 12185058121},
        {1, 2, 3, 4, 5, 7, 55, 111, 141, 191, 343, 434, 777, 868, 1441, 7667, 7777, 22022, 39893, 74647, 168861, 808808, 909909, 1867681, 3097903, 4232324, 4265624, 4298924, 4516154, 4565654},
        {1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596, 9470749, 61255216, 230474032, 466828664, 485494584, 638828836, 657494756, 858474858, 25699499652, 40130703104, 45862226854, 61454945416, 64454545446},
        {1, 2, 3, 4, 5, 6, 7, 9, 121, 292, 333, 373, 414, 585, 3663, 8778, 13131, 13331, 26462, 26662, 30103, 30303, 207702, 628826, 660066, 1496941, 1935391, 1970791, 4198914, 55366355},
        {1, 2, 3, 4, 5, 6, 7, 8, 191, 282, 373, 464, 555, 646, 656, 6886, 25752, 27472, 42324, 50605, 626626, 1540451, 1713171, 1721271, 1828281, 1877781, 1885881, 2401042, 2434342, 2442442}
    };

public:
    long long kMirror(int k, int n) {
        return accumulate(ans[k - 2], ans[k - 2] + n, 0LL);
    }
};

